package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.ListNode;

/** 
* @ClassName   : Leetcode0148 
* @author      : ganwei 
* @date        : 2020年5月21日 
* @Description : 148. 排序链表 
*/
public class Leetcode0148 {
    /**
     * -解题思路，链表排序
     */
	public ListNode sortList(ListNode head) {
    	if(head == null || head.next == null) {
    		return head;
    	}
    	
    	ListNode fast = head.next, slow = head;
    	while(fast != null && fast.next != null) {
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	
    	ListNode tmp = slow.next;
    	slow.next = null;
    	ListNode left = sortList(head);
    	ListNode right = sortList(tmp);
    	
    	ListNode h = new ListNode(0);
    	ListNode res = h;
    	
    	while(left != null && right != null) {
    		if(left.val < right.val) {
    			h.next = left;
    			left = left.next;
    		}else {
    			h.next = right;
    			right = right.next;
    		}
    		h = h.next;
    	}
    	
    	h.next = left != null ? left : right;
    	return res.next;
    }
	
	public static void main(String[] args) {
		
	}
}
